#include "stdafx.h"
#include "graph.h"

using std::vector;

CGraph::CGraph( int _cV, int _cE, Type _type )
	: cV( _cV ), cE( 0 ), type( _type ) {

	if( _type == Matrix ) {

		gMatrix = new int * [ _cV ];

		for ( int i=0; i<_cV; ++i ) {

			gMatrix[ i ] = new int[ _cE ];

			for ( int j=0; j<_cE; ++j ) {

				gMatrix[ i ][ j ] = 0;
			}
		}

	} else {

		cE = _cE;
	}
}

CGraph::~CGraph() {

	if( type == Matrix ) {

		for ( int i=0; i<cV; ++i ) {

			delete [] gMatrix[i];
		}

		delete [] gMatrix;

	} else {
	

	}
}

int CGraph::GetCountV() {


	return cV;
}

int CGraph::GetCountE() {


	return cE;
}

int CGraph::GetWeight( int vSrc, int vDst ) {

	if ( vSrc <= cV && vDst <= cV ) {

		if( type == Matrix ) {

			for ( int  i=0; i<cE; ++i ) {

				if ( gMatrix[ vSrc ][ i ] > 0 ) {

					if( gMatrix[ vDst ][ i ] < 0 ) {


						return gMatrix[ vSrc ][ i ];
					}
				}
			}

		} else {

			for ( int  i=0; i<cE; ++i ) {

				if ( gMatrix[ vSrc ][ i ] > 0 ) {

					if( gMatrix[ vDst ][ i ] < 0 ) {


						return gMatrix[ vSrc ][ i ];
					}
				}
			}
		}
	}


	return INT_MAX;
}

vector< int > CGraph::GetNeighbours( int v ) {

	vector< int > vertices;

	if ( v <= cV ) {

		if( type == Matrix ) {

			for ( int  i=0; i<cE; ++i ) {

				if ( gMatrix[ v ][ i ] > 0 ) {

					for ( int  j=0; j<cV; ++j ) {

						if( gMatrix[ j ][ i ] < 0 ) {
						
							vertices.push_back( j );
						}
					}
				}
			}

		} else {
		
			vertices = gLists[ v ];
		}
	}


	return vertices;
}

bool CGraph::AddEdge( int vSrc, int vDst, int weight ) {

	if ( vSrc <= cV && vDst <= cV && weight >= 0 ) {

		if( type == Matrix ) {

			gMatrix[ vSrc ][ cE ] = weight;
			gMatrix[ vDst ][ cE ] = -weight;

			++cE;


			return true;
	
		} else {

			gLists[ vSrc - 1 ].push_back( vDst - 1 );


			return true;
		}
	}


	return false;
}

bool CGraph::AddNegEdge( int vSrc, int vDst, int weight ) {

	if ( vSrc <= cV && vDst <= cV ) {

		if( type == Matrix ) {

			gMatrix[ vSrc ][ cE ] = -weight;
			gMatrix[ vDst ][ cE ] = weight;

			++cE;


			return true;

		} else {

			gLists[ vSrc - 1 ].push_back( vDst - 1 );


			return true;
		}
	}


	return false;
}

bool CGraph::HaveNegCycle() {


	return false;
}

bool CGraph::IsConnected() {

	bool * connected = new bool[ cV ];
	vector< int > neighbours;


	connected[ 0 ] = true;

	neighbours = GetNeighbours( 0 );

	DFS( connected, neighbours );

	for ( int i=0; i<cV; ++i ) {

		if( !connected[ i ] ) {


			return false;
		}
	}


	return true;
}

void CGraph::DFS( bool * connected, vector< int > neighbours ) {

	vector< int >::iterator itr;


	for ( itr=neighbours.begin(); itr<neighbours.end(); ++itr ) {

		if ( !connected[ *itr ] ) {

			connected[ *itr ] = true;

			DFS( connected, neighbours );
		}
	}
}